/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年03月06日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>
using namespace std;


class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        if(n == 0)
            return 0;

        vector<int> dp(n);
        for(int i = 0; i < n; i++){
            dp[i] = triangle[n-1][i];
        }

        for(int i = n - 2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[j] = min(dp[j] + triangle[i][j], dp[j+1] + triangle[i][j]);
            }
        }

        return dp[0];
    }
};
